package com.mango.leet.code.middle;

import java.util.*;
/**
 * 241. 为运算表达式设计优先级
 */
/**
 * 给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：expression = "2-1-1"
 * 输出：[0,2]
 * 解释：
 * ((2-1)-1) = 0
 * (2-(1-1)) = 2
 * 示例 2：
 *
 * 输入：expression = "2*3-4*5"
 * 输出：[-34,-14,-10,-10,10]
 * 解释：
 * (2*(3-(4*5))) = -34
 * ((2*3)-(4*5)) = -14
 * ((2*(3-4))*5) = -10
 * (2*((3-4)*5)) = -10
 * (((2*3)-4)*5) = 10
 *  
 *
 * 提示：
 *
 * 1 <= expression.length <= 20
 * expression 由数字和算符 '+'、'-' 和 '*' 组成。
 * 输入表达式中的所有整数值在范围 [0, 99] 
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/different-ways-to-add-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LC241 {
    public static void main(String[] args) {
        String expression = "21-1-11*2";
        System.out.println(new Solution().diffWaysToCompute(expression));
    }

    static class Solution {
        // 存放表达式和结果的map
        private Map<String,List<Integer>> resultMap = new HashMap<>();
        public List<Integer> diffWaysToCompute(String expression) {
            if(resultMap.containsKey(expression)){
                return resultMap.get(expression);
            }
            List<Integer> res = new ArrayList<>();
            for(int i=0;i<expression.length();i++){
                char c = expression.charAt(i);
                // 遇到计算符
                if(c == '+' || c == '-' || c == '*'){
                    // 先递归算左边
                    List<Integer> left = diffWaysToCompute(expression.substring(0,i));
                    // 再递归算右边
                    List<Integer> right = diffWaysToCompute(expression.substring(i+1));
                    // 计算最后的结果，并加入到res集合中
                    for(int l : left){
                        for(int r : right){
                            if(c == '+'){
                                res.add(l + r);
                            }else if(c == '-'){
                                res.add(l - r);
                            }else if(c == '*'){
                                res.add(l * r);
                            }
                        }
                    }
                }
            }
            // expression表达式中无符号，则直接保存到结果中
            if(res.isEmpty()){
                res.add(Integer.parseInt(expression));
            }
            // 将表达式对应的结算结果放到map中，后续相同表达式能快速得到结果
            resultMap.put(expression,res);
            return res;
        }
    }
}
/**
 * 2022-03-06
 * 思路：
 * 遇到计算符号，先递归计算左边的结果，再递归计算右边的结果
 * 将结果记录到res集合中
 */
